14.1. skuska Kral

ja som mal dnes

1. definujte co je cesta, nakreslite graf na 6 vrcholoch, v ktorom medzi kazdymi dvoma vrcholmi existuju preve dve cesty

2. dokza ze nemoze nastat remiza v hre hex

3. najdite vsetky neizomorfne grafy so skorem (3,3,3,3,3,3) a dokazte ze ziadne ine neexistuju (navod: pouzite doplnok)

4. v mnozine (1..120) najdite vsetky bezstvorcove slova. stvorcove slova su take ktore obsahuju ako delitela druhu mocninu cisla vacsieho ako 1 (napr. 4,9,16...). 42 je bezstvorcove, ale 50 nie je. vyuzite pincip inkluze a exkluze.

ten hex ma uplne dorazil to som vobec necakal ze tam bude, ale mam to uspesne za sebou.

1. Definujte proste zobrazenie a zobrazenie "na" z mnoziny X do mnoziny Y. Najdite priklad mnoziny X a zobrazenia f: X -> X, ktore je na, ale nie je proste. (Take zobrazenie skutocne existujte.)

2. Sformulujte a dokazte Spernerovu vetu o maximalnej velkosti systemu nezavislych podmnozin n-prvkovej mnoziny.

3. Mozu mat dva Grafy G1 a G2 rovnake skore, pokial
   (a) G1 je suvisly, G2 nie je suvisly;
   (b) G1 je 2-suvisly (vrcholovo), ziadny komponent G2 nie je 2-suvisly;
   (c) G1 je strom, G2 nie je suvisly;
   (d) G1 nie je rovinny, G2 je strom?

4. Dokazte, ze lubovolny rovinny graf je indukovanym podgrafom nejakej rovinnej triangulacie.

Ja som dostal 1, aj ked som nenasiel dobre neproste zobrazenie "na". Povedal som ze X = R a f(x) = tg x, ale tangens nie je definovany na celom R, takze to nebolo dobre. Spravne by bolo zobrat za X R bez bodov pre ktore tangens nie je definovany. Alebo este lepsie je X = N a f(x) = dolna cela cast (n+1)/2.
Co sa tyka 3., nasiel som pre kazdu dvojicu take grafy, ktore mali rovnake skore, a asi to bolo dobre.